n=1000;
m=126;
road=[|702,703,8245|
797,798,6588|
145,146,3252|
223,224,939|
898,899,7664|
440,441,335|
774,775,2432|
42,43,45|
310,311,2244|
34,35,4591|
497,498,8049|
37,38,4957|
795,796,3976|
991,992,7337|
947,948,7246|
43,44,2810|
107,108,3592|
170,171,7132|
695,696,9349|
631,632,9766|
373,374,7568|
232,233,4492|
463,464,3190|
325,326,6629|
203,204,9941|
105,106,4624|
512,513,5734|
155,156,5683|
98,99,124|
378,379,2708|
598,599,5821|
307,308,3467|
23,24,8369|
468,469,8951|
972,973,3736|
596,597,448|
535,536,1825|
887,888,4254|
722,723,1305|
241,242,4488|
199,200,2640|
997,998,8783|
267,268,4162|
390,391,1772|
288,289,9492|
960,961,7447|
939,940,3806|
462,463,3610|
952,953,4808|
393,394,549|
980,981,3192|
566,567,5603|
515,516,5483|
583,584,9133|
995,996,865|
324,325,1933|
109,110,1854|
537,538,1110|
638,639,1214|
386,387,3330|
662,663,8105|
149,150,7612|
896,897,2744|
269,270,7903|
219,220,5463|
773,774,7982|
854,855,8523|
745,746,6406|
146,147,8501|
645,646,5313|
611,612,4711|
464,465,6460|
523,524,4887|
108,109,1691|
755,756,6978|
112,113,7196|
733,734,3571|
850,851,6057|
592,593,4756|
374,375,3410|
911,912,8803|
303,304,2410|
246,247,4697|
116,117,1777|
320,321,8584|
525,526,4146|
999,1000,9651|
642,643,2685|
86,87,7794|
582,583,6408|
211,212,4005|
758,759,5314|
933,934,9225|
50,51,8856|
453,454,2409|
224,225,5691|
705,706,1111|
351,352,7394|
490,491,3483|
436,437,8444|
58,59,5771|
229,230,7304|
475,476,300|
316,317,1897|
364,365,9783|
499,500,9764|
370,371,2336|
262,263,4540|
962,963,6147|
171,172,9760|
162,163,8656|
546,547,5475|
661,662,5401|
381,382,3916|
250,251,4264|
866,867,3455|
158,159,3191|
313,314,6972|
259,260,6250|
753,754,1366|
994,995,2336|
421,422,8727|
652,653,1770|
210,211,9538|
637,638,9706|
448,449,2969|
244,245,8848|
861,862,6512|
847,848,4321|
362,363,4609|
32,33,3482|
187,188,4434|
902,903,8067|
40,41,1252|
881,882,3895|
555,556,1453|
732,733,1842|
218,219,6873|
857,858,2428|
132,133,6236|
519,520,7222|
920,921,427|
749,750,8658|
903,904,5835|
778,779,2792|
589,590,5066|
106,107,5942|
61,62,1213|
951,952,3608|
358,359,4105|
623,624,7368|
396,397,3975|
429,430,744|
225,226,3762|
221,222,8525|
549,550,9314|
725,726,6718|
74,75,4590|
686,687,7854|
954,955,989|
3,4,5110|
966,967,7933|
156,157,5271|
342,343,7720|
227,228,2589|
25,26,2772|
264,265,2200|
372,373,9306|
597,598,2744|
242,243,1290|
200,201,2966|
192,193,5596|
829,830,1131|
811,812,6474|
875,876,3195|
614,615,1596|
477,478,8978|
914,915,4292|
716,717,9122|
297,298,9275|
311,312,2635|
82,83,2107|
143,144,7069|
173,174,224|
981,982,4826|
56,57,4377|
677,678,8223|
912,913,9778|
655,656,8436|
492,493,4839|
678,679,8050|
681,682,7858|
377,378,8773|
233,234,7557|
945,946,5602|
831,832,9823|
696,697,4714|
180,181,7480|
152,153,4751|
639,640,7055|
281,282,6119|
788,789,3991|
96,97,3567|
575,576,1405|
560,561,6050|
715,716,2541|
821,822,6362|
84,85,9541|
899,900,2150|
978,979,4362|
897,898,6909|
635,636,1930|
459,460,3761|
787,788,5586|
344,345,3879|
754,755,705|
272,273,9847|
397,398,5196|
128,129,7647|
509,510,2419|
350,351,9261|
273,274,8356|
712,713,5228|
924,925,9567|
392,393,8910|
858,859,1786|
927,928,283|
217,218,1317|
54,55,2521|
786,787,9169|
346,347,5485|
268,269,5228|
159,160,8113|
496,497,4320|
122,123,9878|
9,10,6974|
69,70,4620|
11,12,6916|
240,241,367|
458,459,2182|
353,354,3076|
142,143,2764|
480,481,645|
738,739,1513|
136,137,6889|
984,985,2044|
410,411,7272|
879,880,1482|
543,544,4973|
545,546,3675|
209,210,2637|
476,477,7908|
7,8,4599|
554,555,2550|
441,442,652|
129,130,4916|
728,729,3585|
684,685,3450|
308,309,6067|
835,836,1900|
387,388,9562|
140,141,3325|
329,330,225|
420,421,2594|
505,506,6949|
775,776,6022|
80,81,1515|
433,434,4735|
562,563,6711|
941,942,4368|
279,280,2763|
680,681,144|
963,964,3469|
484,485,1387|
781,782,1484|
618,619,488|
198,199,9220|
287,288,5147|
371,372,2127|
265,266,2204|
752,753,3647|
606,607,2743|
780,781,5321|
807,808,4021|
710,711,9796|
62,63,3003|
504,505,4707|
99,100,1698|
472,473,4511|
304,305,6391|
694,695,5993|
474,475,324|
767,768,1278|
751,752,9278|
89,90,1211|
341,342,4336|
736,737,4307|
706,707,4728|
813,814,6959|
885,886,8944|
93,94,5909|
389,390,8592|
413,414,349|
319,320,3922|
568,569,2400|
557,558,2310|
66,67,3537|
948,949,4903|
532,533,3424|
833,834,5166|
740,741,5213|
814,815,8934|
721,722,2138|
988,989,607|
260,261,4308|
552,553,1431|
586,587,7491|
301,302,2662|
970,971,8656|
168,169,3304|
727,728,3463|
986,987,6208|
946,947,1405|
834,835,2699|
878,879,3859|
355,356,6291|
470,471,9676|
548,549,6454|
94,95,8283|
890,891,9590|
989,990,1169|
485,486,9266|
201,202,5734|
383,384,3412|
388,389,9861|
75,76,5084|
207,208,7933|
590,591,4653|
418,419,9908|
593,594,3511|
135,136,2991|
852,853,9349|
674,675,528|
450,451,5912|
913,914,6783|
345,346,9316|
337,338,9021|
133,134,8856|
826,827,7621|
71,72,1572|
131,132,1059|
713,714,1238|
167,168,7561|
226,227,9318|
59,60,3519|
874,875,2243|
675,676,9979|
202,203,4381|
467,468,5090|
489,490,7780|
668,669,5150|
701,702,6240|
889,890,4449|
352,353,4419|
524,525,6120|
658,659,2653|
194,195,2499|
88,89,9662|
699,700,7252|
768,769,4961|
309,310,8166|
789,790,5127|
38,39,5184|
838,839,4385|
536,537,1194|
692,693,146|
777,778,5679|
401,402,2612|
294,295,9828|
284,285,6026|
125,126,1000|
764,765,2679|
848,849,5004|
321,322,8765|
553,554,5941|
151,152,3207|
664,665,4624|
687,688,6955|
669,670,1365|
925,926,8346|
44,45,4223|
204,205,667|
230,231,1179|
804,805,1191|
955,956,8111|
222,223,549|
493,494,7005|
455,456,3593|
196,197,6951|
394,395,8281|
403,404,9365|
625,626,9713|
185,186,7830|
673,674,6679|
4,5,9843|
944,945,289|
334,335,8378|
215,216,7573|
495,496,2265|
419,420,8833|
741,742,809|
49,50,2605|
442,443,6622|
340,341,2445|
567,568,1820|
544,545,4747|
868,869,188|
366,367,1653|
18,19,4991|
51,52,8291|
206,207,6098|
302,303,7388|
336,337,2834|
627,628,6713|
971,972,7234|
564,565,5482|
452,453,763|
799,800,1848|
14,15,964|
73,74,1066|
330,331,2530|
13,14,6972|
842,843,513|
612,613,6397|
550,551,9236|
603,604,8807|
915,916,4233|
579,580,3621|
27,28,1680|
817,818,736|
431,432,3886|
730,731,1722|
120,121,4029|
77,78,5551|
816,817,6246|
428,429,5576|
765,766,7234|
760,761,2450|
867,868,6669|
382,383,2015|
784,785,3196|
444,445,4940|
757,758,4145|
26,27,8002|
400,401,460|
81,82,9152|
2,3,9588|
938,939,8393|
841,842,6294|
964,965,682|
617,618,1645|
682,683,4240|
115,116,2451|
634,635,4535|
213,214,6183|
434,435,9669|
594,595,4544|
974,975,5672|
828,829,17|
391,392,2701|
48,49,3213|
641,642,1107|
395,396,4860|
690,691,4207|
862,863,5391|
314,315,1890|
141,142,6097|
953,954,1304|
822,823,4398|
113,114,2434|
624,625,8040|
998,999,6374|
335,336,1399|
539,540,2196|
930,931,8993|
134,135,8509|
961,962,1036|
803,804,5936|
256,257,1743|
8,9,21|
906,907,2431|
793,794,9549|
79,80,5273|
163,164,6873|
182,183,5210|
956,957,2410|
836,837,7079|
950,951,2361|
446,447,4219|
563,564,7913|
965,966,8923|
894,895,378|
541,542,688|
517,518,6447|
46,47,2533|
973,974,3617|
154,155,8847|
157,158,277|
608,609,4349|
35,36,5211|
521,522,8288|
21,22,9033|
723,724,6829|
414,415,200|
904,905,7361|
996,997,1454|
249,250,7909|
616,617,8171|
628,629,1330|
278,279,295|
538,539,4565|
666,667,5052|
365,366,8598|
840,841,7232|
776,777,3542|
830,831,87|
714,715,2072|
466,467,5814|
805,806,2210|
734,735,74|
644,645,1235|
919,920,6170|
577,578,919|
306,307,5914|
949,950,1625|
985,986,8418|
895,896,7576|
735,736,5647|
153,154,5773|
312,313,8680|
982,983,812|
934,935,6531|
601,602,41|
742,743,2809|
243,244,2173|
882,883,6391|
486,487,5881|
561,562,7879|
271,272,7082|
30,31,4366|
276,277,8046|
801,802,2007|
252,253,5270|
254,255,6352|
427,428,9692|
184,185,3332|
683,684,2806|
609,610,8457|
619,620,6124|
604,605,8954|
501,502,5239|
711,712,9351|
437,438,1530|
300,301,5548|
578,579,4966|
528,529,1215|
456,457,4680|
457,458,3838|
15,16,3622|
580,581,4041|
632,633,4650|
877,878,4059|
315,316,4605|
451,452,2735|
599,600,1992|
832,833,7969|
975,976,3959|
527,528,3314|
746,747,4591|
851,852,288|
551,552,1010|
178,179,5414|
286,287,9776|
707,708,7071|
60,61,5472|
174,175,1377|
148,149,7967|
55,56,2167|
280,281,3817|
808,809,5871|
660,661,7814|
323,324,9686|
979,980,9574|
556,557,6673|
53,54,4560|
376,377,3853|
424,425,9206|
888,889,6489|
1,2,4734|
164,165,3426|
343,344,1469|
809,810,2543|
983,984,373|
769,770,2367|
275,276,1953|
439,440,1168|
581,582,2573|
39,40,9665|
605,606,7483|
85,86,7450|
766,767,3956|
584,585,8314|
688,689,540|
756,757,2401|
759,760,3225|
629,630,9727|
685,686,8869|
95,96,4813|
231,232,3729|
368,369,3339|
465,466,8333|
67,68,3321|
239,240,1990|
247,248,4042|
19,20,5231|
724,725,3990|
191,192,7827|
369,370,9023|
461,462,8138|
139,140,6406|
859,860,3962|
16,17,7711|
585,586,5567|
837,838,2258|
547,548,606|
176,177,8867|
719,720,5494|
825,826,4708|
782,783,2233|
379,380,3930|
843,844,8170|
507,508,5277|
283,284,7894|
186,187,6244|
327,328,8280|
169,170,4593|
177,178,2392|
648,649,5096|
602,603,1668|
893,894,5814|
922,923,1938|
506,507,1167|
72,73,3588|
290,291,2744|
856,857,5389|
28,29,6359|
110,111,2099|
481,482,6088|
860,861,1861|
921,922,4401|
454,455,7887|
6,7,6520|
993,994,9132|
405,406,1875|
910,911,1307|
406,407,5985|
416,417,2949|
703,704,455|
103,104,3342|
228,229,6237|
417,418,2170|
119,120,5034|
189,190,9618|
188,189,637|
514,515,5047|
347,348,7422|
656,657,3254|
917,918,6597|
322,323,2285|
78,79,5657|
657,658,3725|
91,92,955|
534,535,5664|
731,732,8019|
237,238,397|
518,519,8027|
291,292,8393|
576,577,4364|
190,191,7360|
522,523,3846|
471,472,6933|
620,621,1444|
354,355,310|
404,405,1566|
700,701,8708|
570,571,6448|
45,46,4961|
238,239,9356|
844,845,6075|
820,821,1324|
909,910,6312|
57,58,1402|
526,527,3778|
41,42,835|
880,881,4357|
411,412,6361|
144,145,6566|
349,350,9593|
591,592,3607|
633,634,7677|
779,780,5832|
491,492,1938|
558,559,3264|
220,221,6748|
818,819,3453|
415,416,2680|
449,450,7688|
849,850,5570|
295,296,7740|
22,23,9625|
261,262,7256|
356,357,2048|
172,173,8915|
117,118,1670|
179,180,32|
299,300,32|
709,710,35|
845,846,14|
990,991,26|
513,514,3|
460,461,39|
698,699,24|
193,194,37|
339,340,4|
646,647,24|
508,509,29|
317,318,34|
114,115,34|
729,730,12|
928,929,28|
101,102,34|
425,426,1|
653,654,34|
806,807,19|
976,977,22|
901,902,9|
447,448,32|
166,167,29|
679,680,14|
399,400,38|
926,927,38|
792,793,6|
258,259,35|
47,48,15|
607,608,8|
640,641,33|
839,840,12|
331,332,23|
720,721,39|
654,655,35|
958,959,37|
810,811,31|
160,161,17|
870,871,21|
748,749,35|
20,21,33|
790,791,29|
823,824,22|
815,816,18|
31,32,22|
426,427,15|
772,773,23|
175,176,7|
326,327,18|
380,381,34|
750,751,13|
236,237,22|
900,901,11|
659,660,33|
708,709,2|
423,424,29|
739,740,14|
29,30,5|
565,566,28|
277,278,39|
650,651,25|
494,495,35|
531,532,28|
161,162,35|
864,865,10|
800,801,2|
559,560,33|
855,856,18|
647,648,38|
533,534,25|
630,631,35|
812,813,4|
542,543,3|
794,795,23|
932,933,40|
587,588,3|
615,616,39|
992,993,17|
488,489,26|
52,53,23|
124,125,39|
10,11,32|
747,748,15|
783,784,24|
693,694,1|
289,290,25|
422,423,23|
130,131,23|
338,339,34|
500,501,11|
298,299,10|
802,803,22|
12,13,16|
430,431,28|
929,930,24|
293,294,3|
482,483,33|
150,151,12|
691,692,39|
92,93,9|
916,917,10|
503,504,16|
478,479,16|
636,637,39|
649,650,9|
967,968,16|
332,333,18|
205,206,31|
510,511,28|
197,198,34|
305,306,21|
282,283,24|
689,690,40|
483,484,37|
64,65,1|
357,358,37|
569,570,11|
412,413,14|
234,235,37|
100,101,4|
574,575,2|
771,772,39|
943,944,16|
935,936,31|
516,517,4004|
68,69,4939|
529,530,9155|
667,668,7294|
571,572,1852|
479,480,3147|
216,217,4285|
824,825,9083|
865,866,6971|
137,138,5165|
626,627,1254|
511,512,4045|
296,297,3995|
959,960,4183|
651,652,5564|
270,271,9933|
435,436,5438|
111,112,4728|
957,958,5713|
90,91,2044|
931,932,7845|
573,574,9167|
274,275,8683|
33,34,8300|
520,521,5482|
923,924,2002|
892,893,5891|
530,531,4674|
263,264,2710|
676,677,9769|
363,364,9558|
937,938,9338|
969,970,7483|
257,258,5137|
127,128,5143|
5,6,4691|
763,764,2092|
908,909,5497|
123,124,6827|
672,673,1183|
791,792,6719|
121,122,8440|
118,119,700|
438,439,1364|
165,166,2|
643,644,7765|
235,236,183|
718,719,9310|
671,672,3587|
977,978,653|
384,385,1421|
907,908,4346|
600,601,6343|
762,763,7520|
670,671,3797|
195,196,1485|
876,877,8916|
744,745,197|
884,885,857|
248,249,2507|
502,503,647|
285,286,8498|
873,874,2709|
872,873,9168|
940,941,1295|
445,446,8980|
24,25,7963|
572,573,2330|
704,705,2799|
498,499,381|
443,444,402|
918,919,1517|
318,319,4336|
181,182,3249|
936,937,2738|
328,329,6878|
819,820,1501|
886,887,4568|
871,872,4617|
610,611,7864|
770,771,1301|
665,666,7264|
761,762,5114|
212,213,3179|
407,408,8573|
595,596,8600|
473,474,664|
432,433,2344|
253,254,347|
869,870,1381|
255,256,8703|
398,399,2070|
333,334,4588|
359,360,4368|
17,18,1004|
942,943,8448|
65,66,1103|
697,698,7750|
76,77,8128|
104,105,1940|
385,386,6823|
469,470,8152|
214,215,2769|
361,362,3589|
827,828,6397|
63,64,8953|
883,884,9736|
717,718,1402|
126,127,428|
487,488,6866|
208,209,3956|
726,727,9069|
138,139,1411|
846,847,8481|
588,589,70|
737,738,7566|
798,799,7383|
245,246,869|
83,84,6227|
409,410,4509|
266,267,6286|
613,614,2404|
87,88,38|
375,376,4179|
743,744,4709|
863,864,1349|
251,252,8587|
36,37,4490|
785,786,6155|
102,103,7255|
968,969,8980|
905,906,7952|
97,98,2484|
408,409,1864|
987,988,3704|
540,541,6504|
622,623,2119|
853,854,2334|
348,349,4255|
147,148,1160|
360,361,2431|
891,892,4978|
292,293,7880|
183,184,6461|
367,368,6814|
663,664,2944|
402,403,4227|
796,797,5650|
621,622,4741|
70,71,9337|];